"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def dfs(self, grid: List[List[int]], r0: int, c0: int, r1: int, c1: int) -> 'Node':
        same = True
        for i in range(r0, r1):
            for j in range(c0, c1):
                if grid[i][j] != grid[r0][c0]:
                    same = False
                    break
            if not same: break
        if same: return Node(grid[r0][c0] == 1, True)

        topLeft = self.dfs(grid, r0, c0, (r0 + r1) // 2, (c0 + c1) // 2)
        topRight = self.dfs(grid, r0, (c0 + c1) // 2, (r0 + r1) // 2, c1)
        bottomLeft = self.dfs(grid, (r0 + r1) // 2, c0, r1, (c0 + c1) // 2)
        bottomRight = self.dfs(grid, (r0 + r1) // 2, (c0 + c1) // 2, r1, c1)

        return Node(True, False, topLeft, topRight, bottomLeft, bottomRight)

    def construct(self, grid: List[List[int]]) -> 'Node':
        return self.dfs(grid, 0, 0, len(grid), len(grid[0]))
        